package pro.softzhang.algo.lc400;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

public class LC438_FindAllAnagramsInAString {
    public static void main(String[] args) {
        String p = "aaaaaaaaaaaaa", s = "aaaaaaaaaa";
        List<Integer> l = new LC438_FindAllAnagramsInAString().findAnagrams(s, p);
        System.out.println(JSON.toJSONString(l));
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> anagrams = new ArrayList<>();

        if(s.length() < p.length()) {
            return anagrams;
        }

        int[] counts = new int[26];
        for (int i = 0; i < p.length(); i++) {
            counts[p.charAt(i) - 'a']++;
            counts[s.charAt(i) - 'a']--;
        }

        if(areAllZero(counts)) {
            anagrams.add(0);
        }

        int p1 = p.length(), p2 = p1 - p.length();
        while (p1 < s.length()) {
            counts[s.charAt(p1++) - 'a']--;
            counts[s.charAt(p2++) - 'a']++;
            if(areAllZero(counts)) {
                anagrams.add(p2);
            }
        }

        return anagrams;
    }

    private boolean areAllZero(int[] counts) {
        for (int count : counts) {
            if(count != 0) {
                return false;
            }
        }
        return true;
    }
}
